package practise.alogrithm.gotoSiliconValley.array;

/**
 * find out the K element in A and B element,A and B is sorted arrays.
 *
 * method A
 * first find out the less array, if first element in larger array larger than last element of A and A.length
 * larger K , get a.length + B[K-a.length],
 * note, please note the end boundary, we must set it for exit the loop,
 * set indexA = min(a.length-1, k/2+1) indexB = k-indexA
 * do
 * a[indexA]<b[indexB] (indexA==a.length-1 return b[k-a.length+1], else indexA =(indexA-endA)/2+1 endB=indexB indexB = k-indexA ) //A move right, B move left
 * else
 * a[indexA]>b[indexB] (indexB==b.length-1 return a[k-b.length+1], else indexB=(indexB-endB)/2+1 endA=indexA indexA =K -indexB   ) // B move right, A move left
 *
 * while end, indexA<endA && indexB<endB
 *
 * indexA==endA return a[indexA] else return b[indexB]
 *
 * method B
 * this is the method in the book, it just focus on the array A,
 * left = 0, right =a.length
 * while(left < right)
 *  mid = left + (right-left)/2, indexB = k-mid
 *  if(indexB>b.length || a[mid]<b[indexB])//B is in its or elementA < elementB, shrunk B, enlarge A
 *      left=mid
 *  else// shrunk A, enlarge B
 *      right=mid
 *   ak=min,bk=min;
 *   left-1 >=0,ak=a[left]// not all in B, then get the a[left]
 *   k-left-1>=0,bk=[k-left]// not all in A, then get the b[k-left]
 *   return Max(ak,bk)
 */
public class TopKFromTwoArrays {

}
